Introduction to Computational Thinking

Historic hero: Noam Chomsky

Founders of the cognitive science field

Father of the modern linguistics

Provided a classification for formal grammars

A formal grammar is a mathematical tool for defining a language (e.g. English) according to a finite set of production rules, that allows one to construct any syntactic valid sentence of such language

Types of formal grammars

• regular grammars (the least expressive)

• context-free grammars

• context-sensitive grammars

• recursively enumerable grammars (the most expressive)

All specify constraints on the way one can use terminal and non-terminal symbols

• terminals are elementary symbols of the language (e.g. words), e.g. "write"

• non-terminals (e.g. <sentence>) can be replaced by a combination of terminal and non-terminal symbols

Example of formal grammar

A simple grammar defined using the Backus-Naur form

<sentence> ::= <pronoun> "write"
<pronoun> ::= "I"
<pronoun> ::= "you"

<sentence> ⇒
<pronoun> "write" ⇒
"I" "write"

Meaning: part 1

Computational Thinking and Programming

Definition of computational (Oxford Dictionary): using or relating to computers

A computer (today): electronic device

A computer (before advent of electronic computers): a person who performs mathematical calculations

In this course, with computer we mean any agent (i.e. anything that can act if appropriately instructed, such as a person or a machine) that is able to make calculations and to produce some output starting from input information

Computers

Human computers: in France, creation of mathematical tables for converting values from the old imperial system of measurement to the new metric system

Babbage's Analytical Engine

ENIAC

Meaning: part 2

Computational Thinking and Programming

The word programming stands for programming language

Natural language: ordinary language (e.g. English), either written or oral, that has evolved naturally in humans, usually without a specific and premeditated planning – expressive but ambiguous

Programming language: formal-born languages (Chomsky's context-free languages, usually) - less expressive but not ambiguous by construction

Kinds of languages 1/2

100010110101010000100100000010001000001111111010000000000111011100000110101110000000000000000000000000000000000011000011100000111111101000000010011101110000011010111000000000010000000000000000000000001100001101010011101110110000000100000000000000000000000010111001000000010000000000000000000000001000110100000100000110011000001111111010000000110111011000000111100010111101100110001001110000010100101011101011111100010101101111000011

fib:
    mov edx, [esp+8]
    cmp edx, 0
    ja @f
    mov eax, 0
    ret
    
    @@:
    cmp edx, 2
    ja @f
    mov eax, 1
    ret
    
    @@:
    push ebx
    mov ebx, 1
    mov ecx, 1

    @@:
        lea eax, [ebx+ecx]
        cmp edx, 3
        jbe @f
        mov ebx, ecx
        mov ecx, eax
        dec edx
    jmp @b
    
    @@:
    pop ebx
    ret

Kinds of languages 2/2

unsigned int fib(unsigned int n) {
    if (n <= 0) return 0;
    else if (n <= 2) return 1;
    else {
        unsigned int a,b,c;
        a = 1;
        b = 1;
        while (1) {
            c = a + b;
            if (n <= 3) return c;
            a = b;
            b = c;
            n--;
        }
    }
}

The function for calculating the nth Fibonacci number takes as input an integer "n". If "n" is less than or equal to 0, then 0 is returned as result. Otherwise, if "n" is less than or equal to 2, then 1 is returned. Otherwise, in all the other cases, associate the value "1" to two distinct variables "a" and "b". Then, repeat indefinitely the following operations: set the variable "c" as the sum of "a" plus "b"; if "n" is less than or equal to 3 then return "c", otherwise assign the value of "b" to "a" and the value of "c" to "b", and finally decrease the value of "n" by 1 before repeating.

Meaning: part 3

Computational Thinking and Programming

To think (definition, Oxford Dictionary): use one's mind actively to form connected ideas

1. Agree on which language to use for the communication between us and a computer (either human or machine)

2. Think about possible instructions that, if followed systematically, can return the expected result to a certain problem

Abstraction is the key

Identify patterns that depict a possible solution for a set of abstractly-homogeneous situations

Reuse the same strategy for reaching our goal, if that strategy has been successful in the past

What is Computational Thinking

An approach for solving problems, designing systems and understanding human behaviour that draws on concepts fundamental to computing

Reshape the abstractions we have ingested as consequence of our life experiences – that we are unconsciously reusing

Being again fully conscious of such abstractions, we can use an appropriate language for making them understandable to a computer, in order to automatise them

Final goal of Computational Thinking: think like a Computer Scientist, even when dealing with common tasks